package leetcode.N701_N800;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/11/30 8:42 下午
 */
public class N767 {

    public String reorganizeString(String S) {
        // 假设S的长度为n, n ≥ 1  则可以得到
        // 1. n % 2 = 0时,  S中能容纳的最大重复字母数量为 n/2
        // 2. n % 2 = 1时,  S中能容纳的最大重复字母数量为 n/2 + 1
        // 由上述1和2可以得出  长度为n(n ≥ 1)的字符串S中最多可以容纳重复字母数量为 (n >> 1) + (n & 1)

        int length = S.length();
        if (length <= 2) {
            return S;
        }
        int maxCount = (length >> 1) + (length & 1);

        // 只包含小写字母  所以使用一个26长度的数组计数
        int[] counts = new int[26];
        for (int i = 0; i < length; i++) {
            int index = S.charAt(i) - 'a';

            int newValue = counts[index]++;
            if (newValue > maxCount) {
                return "";
            }
            counts[i] = newValue;
        }
        // todo 思路断裂


        return null;


    }
}
